package test;

/**
 * @author Marioszk
 * 判断是否子序列
 * 链接：https://www.nowcoder.com/questionTerminal/5382ff24fbf34a858b15f93e2bd85307?f=discussion
 * 来源：牛客网
 * <p>
 * 给定两个字符串 s和 t ，判断 s是否为 t 的子序列。
 * <p>
 * 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度n ~= 500,000），而 s 是个短字符串（长度 <=100）。
 * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
 * <p>
 * 进阶：时间复杂度O(n) O(n) ，空间复杂度O(n) O(n)
 * <p>
 * 输入：
 * 共两行，第一行为字符串s,  第二行为字符串t
 * <p>
 * 字符串t的长度 1<=n<=500000
 * <p>
 * 字符串s的长度 1<=m<=100
 * <p>
 * 输出：输出true或者是false，true表示是s是t的子序列，false表示s不是t的子序列
 */
public class IsSubSequence_判断是否子序列 {

    public static void main(String[] args) {
        String s = "abbcc";
        String t = "ahbbgdc";
        System.out.println(sIsSubSequenceOfT2(s, t));
    }


    private static boolean sIsSubSequenceOfT2(String s, String t) {
        int count = 0;
        int index = 0;
        boolean tIsEnd = false;
        for (int i = 0; i < s.length(); i++) {
            if (tIsEnd) {
                break;
            }

            if (t.substring(index).contains(s.substring(i, i + 1))) {
                // 最长序列是否已经到结尾
                if (t.indexOf(s.substring(i, i + 1)) == t.length() - 1) {
                    tIsEnd = true;
                } else {
                    index += t.substring(index).indexOf(s.substring(i, i + 1));
                }

                count++;
            } else {
                break;
            }
        }
        return count == s.length();
    }
}
